home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxnfa.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  19KB  |  854 lines
  1. /*    Copyright (C) 1995, 1996 Tom Lord
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU Library General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU Library General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU Library General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  16.  * Boston, MA 02111-1307, USA. 
  17.  */
  18.  
  19.  
  20. /*
  21.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  22.  */
  23.  
  24.  
  25. #include "rxall.h"
  26. #include "rxnfa.h"
  27.  
  28.  
  29.  
  30. #define remalloc(M, S) (M ? realloc (M, S) : malloc (S))
  31.  
  32.  
  33. /* {Low Level Data Structure Code}
  34.  */
  35.  
  36. /* Constructs a new nfa node. */
  37. #ifdef __STDC__
  38. struct rx_nfa_state *
  39. rx_nfa_state (struct rx *rx)
  40. #else
  41. struct rx_nfa_state *
  42. rx_nfa_state (rx)
  43.      struct rx *rx;
  44. #endif
  45. {
  46.   struct rx_nfa_state * n = (struct rx_nfa_state *)malloc (sizeof (*n));
  47.   if (!n)
  48.     return 0;
  49.   rx_bzero ((char *)n, sizeof (*n));
  50.   n->next = rx->nfa_states;
  51.   rx->nfa_states = n;
  52.   return n;
  53. }
  54.  
  55.  
  56. #ifdef __STDC__
  57. static void
  58. rx_free_nfa_state (struct rx_nfa_state * n)
  59. #else
  60. static void
  61. rx_free_nfa_state (n)
  62.   struct rx_nfa_state * n;
  63. #endif
  64. {
  65.   free ((char *)n);
  66. }
  67.  
  68.  
  69. /* This adds an edge between two nodes, but doesn't initialize the 
  70.  * edge label.
  71.  */
  72.  
  73. #ifdef __STDC__
  74. struct rx_nfa_edge * 
  75. rx_nfa_edge (struct rx *rx,
  76.          enum rx_nfa_etype type,
  77.          struct rx_nfa_state *start,
  78.          struct rx_nfa_state *dest)
  79. #else
  80. struct rx_nfa_edge * 
  81. rx_nfa_edge (rx, type, start, dest)
  82.      struct rx *rx;
  83.      enum rx_nfa_etype type;
  84.      struct rx_nfa_state *start;
  85.      struct rx_nfa_state *dest;
  86. #endif
  87. {
  88.   struct rx_nfa_edge *e;
  89.   e = (struct rx_nfa_edge *)malloc (sizeof (*e));
  90.   if (!e)
  91.     return 0;
  92.   e->next = start->edges;
  93.   start->edges = e;
  94.   e->type = type;
  95.   e->dest = dest;
  96.   return e;
  97. }
  98.  
  99.  
  100. #ifdef __STDC__
  101. static void
  102. rx_free_nfa_edge (struct rx_nfa_edge * e)
  103. #else
  104. static void
  105. rx_free_nfa_edge (e)
  106.      struct rx_nfa_edge * e;
  107. #endif
  108. {
  109.   free ((char *)e);
  110. }
  111.  
  112.  
  113. /* This constructs a POSSIBLE_FUTURE, which is a kind epsilon-closure
  114.  * of an NFA.  These are added to an nfa automaticly by eclose_nfa.
  115.  */  
  116.  
  117. #ifdef __STDC__
  118. static struct rx_possible_future * 
  119. rx_possible_future (struct rx * rx,
  120.          struct rx_se_list * effects)
  121. #else
  122. static struct rx_possible_future * 
  123. rx_possible_future (rx, effects)
  124.      struct rx * rx;
  125.      struct rx_se_list * effects;
  126. #endif
  127. {
  128.   struct rx_possible_future *ec;
  129.   ec = (struct rx_possible_future *) malloc (sizeof (*ec));
  130.   if (!ec)
  131.     return 0;
  132.   ec->destset = 0;
  133.   ec->next = 0;
  134.   ec->effects = effects;
  135.   return ec;
  136. }
  137.  
  138.  
  139. #ifdef __STDC__
  140. static void
  141. rx_free_possible_future (struct rx_possible_future * pf)
  142. #else
  143. static void
  144. rx_free_possible_future (pf)
  145.      struct rx_possible_future * pf;
  146. #endif
  147. {
  148.   free ((char *)pf);
  149. }
  150.  
  151.  
  152. #ifdef __STDC__
  153. static void
  154. rx_free_nfa_graph (struct rx *rx)
  155. #else
  156. static void
  157. rx_free_nfa_graph (rx)
  158.      struct rx *rx;
  159. #endif
  160. {
  161.   while (rx->nfa_states)
  162.     {
  163.       while (rx->nfa_states->edges)
  164.     {
  165.       switch (rx->nfa_states->edges->type)
  166.         {
  167.         case ne_cset:
  168.           rx_free_cset (rx->nfa_states->edges->params.cset);
  169.           break;
  170.         default:
  171.           break;
  172.         }
  173.       {
  174.         struct rx_nfa_edge * e;
  175.         e = rx->nfa_states->edges;
  176.         rx->nfa_states->edges = rx->nfa_states->edges->next;
  177.         rx_free_nfa_edge (e);
  178.       }
  179.     } /* while (rx->nfa_states->edges) */
  180.       {
  181.     /* Iterate over the partial epsilon closures of rx->nfa_states */
  182.     struct rx_possible_future * pf = rx->nfa_states->futures;
  183.     while (pf)
  184.       {
  185.         struct rx_possible_future * pft = pf;
  186.         pf = pf->next;
  187.         rx_free_possible_future (pft);
  188.       }
  189.       }
  190.       {
  191.     struct rx_nfa_state *n;
  192.     n = rx->nfa_states;
  193.     rx->nfa_states = rx->nfa_states->next;
  194.     rx_free_nfa_state (n);
  195.       }
  196.     }
  197. }
  198.  
  199.  
  200.  
  201. /* {Translating a Syntax Tree into an NFA}
  202.  *
  203.  */
  204.  
  205.  
  206. /* This is the Thompson regexp->nfa algorithm. 
  207.  * It is modified to allow for `side-effect epsilons.'  Those are
  208.  * edges that are taken whenever a similarly placed epsilon edge 
  209.  * would be, but which also imply that some side effect occurs 
  210.  * when the edge is taken.
  211.  *
  212.  * Side effects are used to model parts of the pattern langauge 
  213.  * that are not regular.
  214.  */
  215.  
  216. #ifdef __STDC__
  217. int
  218. rx_build_nfa (struct rx *rx,
  219.           struct rexp_node *rexp,
  220.           struct rx_nfa_state **start,
  221.           struct rx_nfa_state **end)
  222. #else
  223. int
  224. rx_build_nfa (rx, rexp, start, end)
  225.      struct rx *rx;
  226.      struct rexp_node *rexp;
  227.      struct rx_nfa_state **start;
  228.      struct rx_nfa_state **end;
  229. #endif
  230. {
  231.   struct rx_nfa_edge *edge;
  232.  
  233.   /* Start & end nodes may have been allocated by the caller. */
  234.   *start = *start ? *start : rx_nfa_state (rx);
  235.  
  236.   if (!*start)
  237.     return 0;
  238.  
  239.   if (!rexp)
  240.     {
  241.       *end = *start;
  242.       return 1;
  243.     }
  244.  
  245.   *end = *end ? *end : rx_nfa_state (rx);
  246.  
  247.   if (!*end)
  248.     {
  249.       rx_free_nfa_state (*start);
  250.       return 0;
  251.     }
  252.  
  253.   switch (rexp->type)
  254.     {
  255.     case r_cset:
  256.       edge = rx_nfa_edge (rx, ne_cset, *start, *end);
  257.       (*start)->has_cset_edges = 1;
  258.       if (!edge)
  259.     return 0;
  260.       edge->params.cset = rx_copy_cset (rx->local_cset_size,
  261.                     rexp->params.cset);
  262.       if (!edge->params.cset)
  263.     {
  264.       rx_free_nfa_edge (edge);
  265.       return 0;
  266.     }
  267.       return 1;
  268.  
  269.     case r_string:
  270.       {
  271.     if (rexp->params.cstr.len == 1)
  272.       {
  273.         edge = rx_nfa_edge (rx, ne_cset, *start, *end);
  274.         (*start)->has_cset_edges = 1;
  275.         if (!edge)
  276.           return 0;
  277.         edge->params.cset = rx_cset (rx->local_cset_size);
  278.         if (!edge->params.cset)
  279.           {
  280.         rx_free_nfa_edge (edge);
  281.         return 0;
  282.           }
  283.         RX_bitset_enjoin (edge->params.cset, rexp->params.cstr.contents[0]);
  284.         return 1;
  285.       }
  286.     else
  287.       {
  288.         struct rexp_node copied;
  289.         struct rx_nfa_state * shared;
  290.  
  291.         copied = *rexp;
  292.         shared = 0;
  293.         copied.params.cstr.len--;
  294.         copied.params.cstr.contents++;
  295.         if (!rx_build_nfa (rx, &copied, &shared, end))
  296.           return 0;
  297.         copied.params.cstr.len = 1;
  298.         copied.params.cstr.contents--;
  299.         return rx_build_nfa (rx, &copied, start, &shared);
  300.       }
  301.       }
  302.  
  303.     case r_opt:
  304.       return (rx_build_nfa (rx, rexp->params.pair.left, start, end)
  305.           && rx_nfa_edge (rx, ne_epsilon, *start, *end));
  306.  
  307.     case r_plus:
  308.       {
  309.     struct rx_nfa_state * star_start = 0;
  310.     struct rx_nfa_state * star_end = 0;
  311.     struct rx_nfa_state * shared;
  312.  
  313.     shared = 0;
  314.     if (!rx_build_nfa (rx, rexp->params.pair.left, start, &shared))
  315.       return 0;
  316.     return (rx_build_nfa (rx, rexp->params.pair.left,
  317.                   &star_start, &star_end)
  318.         && star_start
  319.         && star_end
  320.         && rx_nfa_edge (rx, ne_epsilon, star_start, star_end)
  321.         && rx_nfa_edge (rx, ne_epsilon, shared, star_start)
  322.         && rx_nfa_edge (rx, ne_epsilon, star_end, *end)
  323.         && rx_nfa_edge (rx, ne_epsilon, star_end, star_start));
  324.       }
  325.  
  326.     case r_interval:
  327.     case r_star:
  328.       {
  329.     struct rx_nfa_state * star_start = 0;
  330.     struct rx_nfa_state * star_end = 0;
  331.     return (rx_build_nfa (rx, rexp->params.pair.left,
  332.                   &star_start, &star_end)
  333.         && star_start
  334.         && star_end
  335.         && rx_nfa_edge (rx, ne_epsilon, star_start, star_end)
  336.         && rx_nfa_edge (rx, ne_epsilon, *start, star_start)
  337.         && rx_nfa_edge (rx, ne_epsilon, star_end, *end)
  338.  
  339.         && rx_nfa_edge (rx, ne_epsilon, star_end, star_start));
  340.       }
  341.  
  342.     case r_cut:
  343.       {
  344.     struct rx_nfa_state * cut_end = 0;
  345.  
  346.     cut_end = rx_nfa_state (rx);
  347.     if (!(cut_end && rx_nfa_edge (rx, ne_epsilon, *start, cut_end)))
  348.       {
  349.         rx_free_nfa_state (*start);
  350.         rx_free_nfa_state (*end);
  351.         if (cut_end)
  352.           rx_free_nfa_state (cut_end);
  353.         return 0;
  354.       }
  355.     cut_end->is_final = rexp->params.intval;
  356.     return 1;
  357.       }
  358.  
  359.     case r_parens:
  360.       return rx_build_nfa (rx, rexp->params.pair.left, start, end);
  361.  
  362.     case r_concat:
  363.       {
  364.     struct rx_nfa_state *shared = 0;
  365.     return
  366.       (rx_build_nfa (rx, rexp->params.pair.left, start, &shared)
  367.        && rx_build_nfa (rx, rexp->params.pair.right, &shared, end));